//在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只
//能放在更大的盘子上面)。移动圆盘时受到以下限制: 
//(1) 每次只能移动一个盘子; 
//(2) 盘子只能从柱子顶端滑出移到下一根柱子; 
//(3) 盘子只能叠在比它大的盘子上。 
//
// 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。 
//
// 你需要原地修改栈。 
//
// 示例1: 
//
//  输入：A = [2, 1, 0], B = [], C = []
// 输出：C = [2, 1, 0]
// 
//
// 示例2: 
//
//  输入：A = [1, 0], B = [], C = []
// 输出：C = [1, 0]
// 
//
// 提示: 
//
// 
// A中盘子的数目不大于14个。 
// 
// Related Topics 递归 
// 👍 40 👎 0


package com.yun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class HanotaLcci {
    public static void main(String[] args) {
        Solution solution = new HanotaLcci().new Solution();
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        List<Integer> c = new ArrayList<>();
        for (int i = 30; i >= 0; i--) {
            a.add(i);
        }
        solution.hanota(a, b, c);
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            move(A.size(), A, B, C);
        }

        private void move(int num, List<Integer> original, List<Integer> middle, List<Integer> target) {
            if (num == 1) {
                target.add(original.remove(original.size() -1));
                return ;
            }
            move(num-1, original, target, middle);
            target.add(original.remove(original.size() - 1));
            move(num-1, middle, original, target);

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}